package com.da.javatest.interview.session1;

/**
 * @author chenlida
 * @date 2020/3/25 19:30
 * @description 斐波那契数列
 */
public class Test05 {
    public static void main(String[] args) {
        System.out.println(getStep(5));
        System.out.println(getStep2(5));
    }

    private static int getStep(int n) {
        if (n < 3) {
            return n;
        }
        return getStep(n - 1) + getStep(n - 2);
    }

    private static int getStep2(int n) {
        if (n < 3) {
            return n;
        }
        // 上1次的值
        int lastOne = 2;
        // 上2次的值
        int lastTwo = 1;
        int sum = 0;

        for (int i = 3; i <= n; i++) {
            sum = lastOne + lastTwo;
            lastTwo = lastOne;
            lastOne = sum;
        }
        return sum;
    }
}
